package NowCoder;

//二叉搜索树与双向链表
//输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。
public class JZ36 {
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null) {
            return null;
        }
        //先走到最左子节点
        TreeNode leftHead = Convert(pRootOfTree.left);
        TreeNode leftTail = leftHead;
        //将尾节点，遍历到最后
        while (leftTail != null && leftTail.right != null ) {
            leftTail = leftTail.right;
        }
        //将左子树子节点与根节点连接
        if (leftTail != null) {
            pRootOfTree.left = leftTail;
            leftTail.right = pRootOfTree;
        }
        //右子树头节点
        TreeNode rightHead = Convert(pRootOfTree.right);
        //右子树头节点与根节点连接
        if (rightHead != null) {
            pRootOfTree.right = rightHead;
            rightHead.left = pRootOfTree;
        }
        return leftHead == null ? pRootOfTree : leftHead;
    }

    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;

        }
    }
}
